package sorting

import "gitee.com/guuzaa/sorting/constraints"

func InsertionSort[T constraints.Ordered](arr []T) []T {
	for i := 1; i < len(arr); i++ {
		cur := arr[i]
		pos := i

		for pos > 0 && cur < arr[pos-1] {
			arr[pos] = arr[pos-1]
			pos--
		}

		arr[pos] = cur
	}

	return arr
}

func BinaryInsertionSort[T constraints.Ordered](arr []T) []T {
	for i := 1; i < len(arr); i++ {
		cur := arr[i]
		pos := i

		left, right := 0, i
		for left < right {
			mid := left + (right-left)/2
			if arr[mid] >= cur {
				right = mid
			} else {
				left = mid + 1
			}
		}

		for j := pos; j > left; j-- {
			arr[j] = arr[j-1]
		}
		arr[left] = cur
	}

	return arr
}
